using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Hive.Bot.Behaviours;
using Hive.Bot.Tasks;
using Hive.Core;

namespace Hive.Bot
{
    public class HiveController: IBot
    {
        public HiveController()
        {
            behaviours = FillBehaviours();
        }

        List<IBehaviour> behaviours;

        private List<IBehaviour> FillBehaviours()
        {
            var result = new List<IBehaviour>();
            result.Add(new ExploreBehavior(15));
            result.Add(new FarmBehavior());
            result.Add(new AttackHiveBehavior());
            result.Add(new UtilityBehavior());
            result.Add(new RoamBehavior());
            result.Add(new AttackEnemyBehavior());
            return result;
        }

        public void DoTurn(GameState state)
        {
            Log.Write("Turn start");
            Env.SetState(state);
            try
            {
                Perf.Start("turn");

                Perf.Start("Env.Update and statistics");
                Env.Update();
                Log.WriteStatistics();
                Log.Write("Data filled in.");
                Perf.End("Env.Update and statistics");

                Perf.Start("GenerateTasks");
                var tasks = behaviours.SelectMany(b => b.GenerateTasks()).ToList();
                Log.Write("behaviors calculated {0} tasks created.", tasks.Count);
                Perf.End("GenerateTasks");

                Perf.Start("CalculateEfficiencies");
                var efficiencyMatrix = new int[tasks.Count(), Env.MyAnts.Count];
                CalculateEfficiencies(tasks, efficiencyMatrix);
                Log.WriteEfficiencies(efficiencyMatrix);
                Log.Write("efficiency calculated.");
                Perf.End("CalculateEfficiencies");

                Perf.Start("AssignTasks");
                AssignTasks(efficiencyMatrix, tasks);
                Log.Write("tasks assigned.");
                Perf.End("AssignTasks");

                Perf.Start("Execute tasks");
                var orders = tasks.Where(t => t.IsAssigned).Select(t => t.Execute());
                Perf.End("Execute tasks");

                LogOrders(orders);

                Perf.Start("PerformOrders");
                PerformOrders(orders);
                Perf.End("PerformOrders");

                Log.Write("tasks executed.");

                Perf.End("turn");

                Log.WritePerformance();
            }
            catch (Exception ex)
            {
                Log.Write(ex.ToString());
            }
            Log.Write("Turn end");
        }

        private void LogOrders(IEnumerable<Order> orders)
        {
            Log.Write("Following orders assigned");
            foreach (var o in orders)
            {
                Log.Write("ant id {0} at {1} to {2}", o.Ant.Id, o.Ant.Location, o.Destination);
            }
        }

        private void PerformOrders(IEnumerable<Order> orders)
        {
            var graph = BuildMovementGraph(orders);

            ProcessGraph(graph);

            ExecuteGraph(graph, orders);
        }

        private void ProcessGraph(Dictionary<Location, List<Location>> graph)
        {
            // we can have only single child graph but we allow circular references
            List<Location> toProcess = new List<Location>(graph.Where(p => p.Value.Count > 1).Select(p => p.Key));

            while (toProcess.Any())
            {
                var item = toProcess.First();
                var bestChild = FindLongestQueue(graph, item);

                foreach (var c in graph[item].Where(i => i != bestChild))
                {
                    if (!graph.ContainsKey(c))
                        graph[c] = new List<Location>();

                    graph[c].Add(c);
                    toProcess.Add(c);
                }

                graph[item].Clear();
                graph[item].Add(bestChild);

                toProcess.Remove(item);
            }
        }

        private Location FindLongestQueue(Dictionary<Location, List<Location>> graph, Location item)
        {
            var children = graph[item];

            var max = 0;
            Location result = children.First();
            foreach (var c in children)
            {
                var depth = GetDepth(item, c, graph, 1);
                if (depth > max)
                {
                    max = depth;
                    result = c;
                }
            }

            return result;
        }

        private int GetDepth(Location root, Location current, Dictionary<Location, List<Location>> graph, int depth)
        {
            if (current == root)
                return int.MaxValue;

            if (graph.ContainsKey(current))
                return graph[current].Max(l => GetDepth(root, l, graph, depth + 1));
            else
                return depth;
        }

        private void ExecuteGraph(Dictionary<Location, List<Location>> graph, IEnumerable<Order> orders)
        {
            var activeAnts = graph.Where(p => p.Key != p.Value.First()).Select(p => p.Value.First());

            var toExecute = orders.Where(o => activeAnts.Contains(o.Ant.Location));
            toExecute.ToList().ForEach(o => o.Ant.Move(o.Destination));

            //foreach (var a in activeAnts)
            //{
            //    var order = orders.Where(o => o.Ant.Location == a).Single();
            //    order.Ant.Move(order.Destination);
            //}
        }

        private Dictionary<Location, List<Location>> BuildMovementGraph(IEnumerable<Order> orders)
        {
            var result = new Dictionary<Location, List<Location>>();

            foreach (var o in orders)
            {
                if (!result.ContainsKey(o.Destination))
                {
                    result[o.Destination] = new List<Location>();
                }

                result[o.Destination].Add(o.Ant.Location);
            }

            var withoutOrders = Env.MyAnts.Where(a => !orders.Any(o => o.Ant.Equals(a)));
            foreach (var a in withoutOrders)
            {
                if (!result.ContainsKey(a.Location))
                {
                    result[a.Location] = new List<Location>();
                }

                result[a.Location].Add(a.Location);

            }
            return result;
        }

        private void CheckCollisions(List<Order> toExecute)
        {
            Dictionary<Ant, Location> newLocations = new Dictionary<Ant, Location>();

            foreach (var a in Env.MyAnts)
            {
                newLocations[a] = a.Location;
            }

            foreach (var o in toExecute)
            {
                newLocations[o.Ant] = o.Destination;
            }

            if (newLocations.Values.Distinct().Count() != newLocations.Values.Count)
                throw new ApplicationException("Collision check failed");
        }

        private void LogSkippedAnts(IEnumerable<Location> skippedAnts)
        {
            foreach (var sa in skippedAnts)
            {
                var ant = Env.MyAnts.Where(a => a.Location == sa).Single();
                Log.Write("Ant {0} at {1} doesn't move", ant.Id, ant.Location);
            }
        }

        private void AssignTasks(int[,] efficiencyMatrix, List<ITask> tasks)
        {
            //TODO: improve calculation
            bool[] processedTasks = new bool[efficiencyMatrix.Height()];
            bool[] processedAnts = new bool[efficiencyMatrix.Width()];

            var count = Math.Min(efficiencyMatrix.Height(), efficiencyMatrix.Width());

            //processedAnts.Any(v => !v) && processedTasks.Any(v => !v)
            while (count > 0)
            {
                var max = Max(efficiencyMatrix, processedAnts, processedTasks);
                if (max == null)
                {
                    Log.Write("Cannot find max in matrix:");
                    Log.WriteEfficiencies(efficiencyMatrix, processedAnts, processedTasks);
                }
                if (efficiencyMatrix.At(max) == 0)
                {
                    processedTasks[max.Row] = true;
                    Log.Write("Task {0} index {1} has zero efficiency", tasks[max.Row].ToString(), max.Row);
                }
                else
                {
                    processedAnts[max.Col] = true;
                    processedTasks[max.Row] = true;
                    tasks[max.Row].Assign(Env.MyAnts[max.Col]);
                    Log.Write("Best task {0} index {1} assigned to ant {2} at {3}", tasks[max.Row].ToString(), max.Row, Env.MyAnts[max.Col].Id, Env.MyAnts[max.Col].Location);
                }
                count--;
            }
        }

        private Location Max(int[,] efficiencyMatrix, bool[] processedAnts, bool[] processedTasks)
        {
            int max = -1;
            Location result = null;
            efficiencyMatrix.Iter((r, c, v) =>
                {
                    if (!(processedAnts[c] || processedTasks[r]))
                    {
                        if (v > max)
                        {
                            result = new Location(r, c);
                            max = v;
                        }
                    }
                }
                );

            return result;
        }

        private int GetBestTask(int[,] efficiencyMatrix, int a, bool[] skippedTasks)
        {
            var max = -1;
            int result = 0;
            for (var t = 0; t < efficiencyMatrix.Height(); t++)
            {
                if (skippedTasks[t])
                    continue;

                if (efficiencyMatrix[t, a] > max)
                {
                    max = efficiencyMatrix[t, a];
                    result = t;
                }
            }

            return result;
        }

        private void CalculateEfficiencies(List<ITask> tasks, int[,] efficiencyMatrix)
        {

            //List<List<Tuple<int, int>>> 
            for (int t = 0; t < tasks.Count; t++)
            {
                var efficiencies = tasks[t].CalculateEfficiencies(Env.MyAnts).ToList();
                for (int a = 0; a < efficiencies.Count; a++)
                {
                    efficiencyMatrix[t, a] = efficiencies[a];
                }
            }
        }

        //private void CalculateEfficiencies(List<ITask> tasks, int[,] efficiencyMatrix)
        //{
        //    for (int t = 0; t < tasks.Count; t++)
        //    {
        //        var efficiencies = tasks[t].CalculateEfficiencies(Env.MyAnts).ToList();
        //        for (int a = 0; a < efficiencies.Count; a++)
        //        {
        //            efficiencyMatrix[t, a] = efficiencies[a];
        //        }
        //    }
        //}

    }
}